package algorithm.array;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

/**
 * @Author: Hevery
 * @Description:
 * @Date: Created on 2017/10/3
 * @Modified By:
 */
public class BeautifulNumberLarge {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        long cases = scan.nextLong();
        for (int i = 1; i <= cases; i++) {
            long n = scan.nextLong();
            System.out.println(beautiful(n));
        }



    }
    //O(N*logN) N=10^18
    // 10^18*64
    //10^8 ~= 1s    1年 = 365*24*3600=31536000 s
    //10^18*64/10^8 = 64*10^10=640000000000/31536000=20294年

    //logN*longN*longN = 64 * 64 *64 <<< 64*10^10
    private static long beautiful(long n){
        for(int bits = 64; bits >= 2; bits--){
                long radix = getRadix(n,bits);
                if(radix != -1){
                    return radix;
                }
        }
        //最坏情况下radix为n-1,但是理论上不可能执行下面的return
        throw new IllegalStateException("Should not reach here.");
    }

    /**
     * 使用二分查找来寻找符合条件的radix
     * @param n 带转换数字
     * @param bits radix进制中1的个数
     * @return 如果存在返回进制radix，不存在返回-1
     */
    private static long getRadix(long n, int bits){
        long minRadix = 2;
        long maxRadix = n;//最坏情况加1(最坏情况下为n-1)
        while(minRadix < maxRadix){
            long m = (minRadix + maxRadix - minRadix);//防止大整数相加溢出
            long t = convert(m, bits);
            if(t == n){
                return m;
            } else if (t < n){
                minRadix = m + 1;
            } else {
                maxRadix = n;
            }
        }
        return -1;
    }

    private static long convert(long radix, int bits){
        long component = 1;
        long sum = 0;
        for (int i = 0; i < bits; i++) {
            if(Long.MAX_VALUE - sum < component){
                sum = Long.MAX_VALUE;
            } else {
                sum += component;
            }

            if(Long.MAX_VALUE / component < radix){
                component = Long.MAX_VALUE;
            } else {
                component *= radix;
            }
        }
        return sum;
    }
}
